#pragma once

#include <vector>
#include "nrtypes.h"

using namespace std;

void gcd(QWORD a, QWORD b, QWORD *c1, QWORD *c2)
{
    if(b == 0 || a == 0 || a % b == 0)
	{
		if(b == 0)
		{
			*c1 = 1;
			*c2 = 0;
		}
		else
		{
			*c1 = 0;
			*c2 = 1;
		}
	}
    else
	{
		QWORD t;
		gcd(b, a % b, c1, &t);
		*c2 = *c1 - t * (a / b);
		*c1 = t;
	}
}

template<size_t Q>
class GaloisFieldPrime
{
	vector<QWORD> cache;

	QWORD _invert(QWORD a)
	{
		QWORD c1;
		QWORD c2;
		gcd(a, Q, &c1, &c2);
		c1 = (Q + c1) % Q;
		cache[c1] = a;
		cache[a] = c1;
		return c1;
	}

public:
	GaloisFieldPrime()
	{
		for(int i = 0; i < Q; i ++)
		{
			cache.push_back(~QWORD(0));
		}
	}

	QWORD inverse(QWORD a)
	{
		return cache[a] == ~QWORD(0) ? _invert(a) : cache[a];
	}

	QWORD add(QWORD a, QWORD b)
	{
		return (a + b) % Q;
	}

	QWORD mult(QWORD a, QWORD b)
	{
		return (a * b) % Q;
	}
};

//template<size_t Q>
//class BerlekampMassey
//{
//public:
//
//	void push(QWORD
//};